Gelfond and Lifschitz proposed the notion of a stable model of a logic program. We establish that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has at least one stable model, is Σ11-complete. Due to (...) the equivalences established in the authors' previous nonmonotone rule systems papers ), this applies equally to truth maintenance systems and default logics. (shrink)

Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.) In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements. In this paper we present a recursive nonstandard model of normal open induction with an unbounded set (...) of infinite prime elements. (shrink)

Naturally occurring speech contains only a limited amount of complex recursive structure, and this is reflected in the empirically documented difficulties that people experience when processing such structures. We present a connectionist model of human performance in processing recursive language structures. The model is trained on simple artificial languages. We find that the qualitative performance profile of the model matches human behavior, both on the relative difficulty of center‐embedding and cross‐dependency, and between the processing of (...) these complex recursive structures and right‐branching recursive constructions. We analyze how these differences in performance are reflected in the internal representations of the model by performing discriminant analyses on these representations both before and after training. Furthermore, we show how a network trained to process recursive structures can also generate such structures in a probabilistic fashion. This work suggests a novel explanation of people's limited recursive performance, without assuming the existence of a mentally represented competence grammar allowing unbounded recursion. (shrink)

We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in (...) a finite language. (shrink)

We construct two recursive models of fragments of set theory. We also show that the fragments of Kripke-Platek set theory that prove -induction for -formulas have no recursive models but the standard model of the hereditarily finite sets.

Cumulative evidence suggests that, for children and adolescents, peer relatedness is an essential component of their overall sense of belonging, and correlates with subjective well-being and school-based well-being. However, it remains unclear what the underlying mechanism explaining these relationships is. Therefore, this study examines whether there is a reciprocal effect between school satisfaction and overall life satisfaction (Hypothesis 1), and whether the effect of peer relatedness on life satisfaction is mediated by school satisfaction (Hypothesis 2). A non-recursive model (...) with instrumental variables was tested with econometric and structural equation modeling methodologies, using a cross-sectional sample ofn= 5,619 Chilean early adolescents (49.2% girls), aged 10, 11, and 12 (46.13, 44.99, and 8.88% respectively). Results were highly consistent across methods and supported the hypotheses. First, the findings confirmed a significant reciprocal influence between school satisfaction and overall life satisfaction, with a greater impact from school to life satisfaction. Second, the effect of peer relatedness on overall life satisfaction was fully mediated by school satisfaction. The study further suggests the importance of considering reciprocal effects among domain-specific satisfaction and overall life satisfaction and illustrates the application of non-recursive models for this purpose. (shrink)

We describe a strongly minimal theory S in an effective language such that, in the chain of countable models of S, only the second model has a computable presentation. Thus there is a spectrum of an -categorical theory which is neither upward nor downward closed. We also give an upper bound on the complexity of spectra.

A method for the recursive identification of physiological models of the cardiovascular baroreflex is proposed and applied to the time-varying analysis of vagal and sympathetic activities. The proposed method was evaluated with data from five newborn lambs, which were acquired during injection of vasodilator and vasoconstrictors and the results show a close match between experimental and simulated signals. The model-based estimation of vagal and sympathetic contributions were consistent with physiological knowledge and the obtained estimators of vagal and sympathetic (...) activities were compared to traditional markers associated with baroreflex sensitivity. High correlations were observed between traditional markers and model-based indices. (shrink)

The main result of this paper partially answers a question raised in about the existence of countable just recursively saturated models of Peano Arithmetic with non‐isomorphic automorphism groups. We show the existence of infinitely many countable just recursively saturated models of Peano Arithmetic such that their automorphism groups are not topologically isomorphic. We also discuss maximal open subgroups of the automorphism group of a countable arithmetically saturated model of in a very good interstice.

I survey the syntactic technique of tiering which can be used to restrict the power of a recursion scheme. I show how various results can be obtained entirely proof theoretically without the use of a model of computation.

This paper presents an approach to the belief system based on a computational framework in three levels: first, the logic level with the definition of binary local rules, second, the arithmetic level with the definition of recursive functions and finally the behavioural level with the definition of a recursive construction pattern. Social communication is achieved when different beliefs are expressed, modified, propagated and shared through social nets. This approach is useful to mimic the belief system because the defined (...) functions provide different ways to process the same incoming information as well as a means to propagate it. Our model also provides a means to cross different beliefs so, any incoming information can be processed many times by the same or different functions as it occurs is social nets. (shrink)

This paper, a contribution to “micro set theory”, is the study promised by the first author in [M4], as improved and extended by work of the second. We use the rudimentarily recursive functions and the slightly larger collection of gentle functions to initiate the study of provident sets, which are transitive models of $\mathsf{PROVI}$, a subsystem of $\mathsf{KP}$ whose minimal model is Jensen’s $J_{\omega}$. $\mathsf{PROVI}$ supports familiar definitions, such as rank, transitive closure and ordinal addition—though not ordinal multiplication—and (...) Shoenfield’s unramified forcing. Providence is preserved under directed unions. An arbitrary set has a provident closure, and the extension of a provident $M$ by a set-generic $\mathcal{G}$ is the provident closure of $M\cup\{\mathcal{G}\}$. The improvidence of many models of $\mathsf{Z}$ is shown. The final section uses similar but simpler recursions to show, in the weak system $\mathsf{MW}$, that the truth predicate for $\dot{\varDelta}_{0}$ formulæ is $\Delta_{1}$. (shrink)

In this paper we investigate the properties of automorphism groups of countable short recursively saturated models of arithmetic. In particular, we show that Kaye's Theorem concerning the closed normal subgroups of automorphism groups of countable recursively saturated models of arithmetic applies to automorphism groups of countable short recursively saturated models as well. That is, the closed normal subgroups of the automorphism group of a countable short recursively saturated model of PA are exactly the stabilizers of the invariant cuts of (...) the model which are closed under exponentiation. This Galois correspondence is used to show that there are countable short recursively saturated models of arithmetic whose automorphism groups are not isomorphic as topological groups. Moreover, we show that the automorphism groups of countable short arithmetically saturated models of PA are not topologically isomorphic to the automorphism groups of countable short recursively saturated models of PA which are not short arithmetically saturated. (shrink)

This paper presents an approach to the belief system based on a computational framework in three levels: first, the logic level with the definition of binary local rules, second, the arithmetic level with the definition of recursive functions and finally the behavioural level with the definition of a recursive construction pattern. Social communication is achieved when different beliefs are expressed, modified, propagated and shared through social nets. This approach is useful to mimic the belief system because the defined (...) functions provide different ways to process the same incoming information as well as a means to propagate it. Our model also provides a means to cross different beliefs so, any incoming information can be processed many times by the same or different functions as it occurs is social nets. (shrink)

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive (...) recursive structures, exponential-time structures and structures with honest witnesses. (shrink)

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. (...) In all of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings. (shrink)

Alex has written an excellent thesis in the area of computable model theory. The latter is a subject that nicely combines model-theoretic ideas with delicate recursiontheoretic constructions. The results demand good knowledge of both fields. In his thesis, Alex begins by reviewing the essential model-theoretic facts, especially the Baldwin-Lachlan result about uncountably categorical theories. This he follows with a brief discussion of recursion theory, including mention of the priority method. The deepest part of the thesis concerns the (...) study of the recursive spectrum of an uncountably categorical theory, i.e. the set of n ≤ ! such that the n-th model of the theory (in the Baldwin-Lachlan sense) has a computable presentation. This is a deep and very active area of conteporary research in computable model theory which Alex discusses in considerable detail. The exposition is very good and therefore the thesis makes a nice introduction to the subject for a wide community of logicians. (Sy-David Friedman, Professor of Mathematical Logic, Director of the Kurt Godel Research Center for Mathematical Logic, University of Vienna). (shrink)

We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

The paper builds on both a simply typed term system ${\cal PR}^\omega$ and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains $D_\rho$ supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions ${\cal PR}^{\omega e}$ and PTWP $^e$ are (...) studied that are closed under scvr. The twist are certain type 1 Gödel recursors ${\cal R}_k$ for simultaneous partial primitive recursion. Formally, ${\cal R}_k\vec{g}\vec{H}xi$ denotes a function $f_i \in D_{\iota\to\iota}$ , however, ${\cal R}_k$ is modelled such that $f_i$ is finite, or in other words, a partial sequence. As for PTWP $^e$ , the concept of type $\iota\to\iota$ writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP $^e$ -computable functionals coincide with those definable in ${\cal PR}^{\omega e}$ plus a constant for sequential minimisation. In particular, the functionals definable in ${\cal PR}^{\omega e}$ denoted ${\cal R}^{\omega e}$ can be characterised by a subclass of PTWP $^e$ -computable functionals denoted ${\rm PPR}^{\omega e}$ . Moreover, hierarchies of strictly increasing classes ${\cal R}^{\omega e}_n$ in the style of Heinermann and complexity classes ${\rm PPR}^{\omega e}_n$ are introduced such that $\forall n\ge 0. {\cal R}^{\omega e}_n ={\rm PPR}^{\omega e}_n$ . These results extend those for ${\cal PR}^\omega$ and PTWP [Nig94]. Finally, scvr is employed to define for each type $\sigma$ the enumeration functional $E^\sigma$ of all finite elements of $D_\sigma$. (shrink)

Hird, G.R., Recursive properties of relations on models, Annals of Pure and Applied Logic 63 241–269. We prove general existence theorems for recursive models on which various relations have specified recursive properties. These capture common features of results in the literature for particular algebraic structures. For a useful class of models with new relations R, S, where S is r.e., we characterize those for which there is a recursive model isomorphic to on which the relation (...) corresponding to S remains r.e., while that corresponding to R is not r.e.; immune; hyperimmune. The results are applied to vector spaces, Boolean algebras and abelian groups. In the case of vector spaces, this leads to a new kind supermaximal subspace of V∞. (shrink)

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of (...) models. (shrink)

Mathematics is obviously important in the sciences. And so it is likely to be equally important in any effort that aims to understand God in a scientifically significant way or that aims to clarify the relations between science and theology. The degree to which God has any perfection is absolutely infinite. We use contemporary mathematics to precisely define that absolute infinity. For any perfection, we use transfinite recursion to define an endlessly ascending series of degrees of that perfection. That series (...) rises to an absolutely infinite degree of that perfection. God has that absolutely infinite degree. We focus on the perfections of knowledge, power, and benevolence. Our model of divine infinity thus builds a bridge between mathematics and theology. (shrink)

The Recursive Bayesian Net (RBN) formalism was originally developed for modelling nested causal relationships. In this paper we argue that the formalism can also be applied to modelling the hierarchical structure of mechanisms. The resulting network contains quantitative information about probabilities, as well as qualitative information about mechanistic structure and causal relations. Since information about probabilities, mechanisms and causal relations is vital for prediction, explanation and control respectively, an RBN can be applied to all these tasks. We show in (...) particular how a simple two-level RBN can be used to model a mechanism in cancer science. The higher level of our model contains variables at the clinical level, while the lower level maps the structure of the cell's mechanism for apoptosis. (shrink)

We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models. and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey's Theorem for Pairs.

We show that that every countable model of PA has a conservative extension M with a subset Y such that a certain Σ1(Y)-formula defines in M a subset which is not r. e. relative to Y.

We prove a model theoretic generalization of an extension of the Keisler-Morley theorem for countable recursively saturated models of theories having a K-like model, where K is an inaccessible cardinal.

The article introduces recursive ontology, a general ontology which aims to describe how being is organized and what are the processes that drive it. In order to answer those questions, I use a multidisciplinary approach that combines the theory of levels, philosophy and systems theory. The main claim of recursive ontology is that being is the product of a single recursive process of generation that builds up all of reality in a hierarchical fashion from fundamental physical particles (...) to human societies. To support this assumption, I provide the general laws and the basic principles of recursive ontology as well as a semi-formalised model of the theory based on a recursive generative grammar. Recursive ontology not only actively promotes a multidisciplinary investigation of reality, but also can be used as a general framework to develop future domain-specific theories. (shrink)

The first example of a simultaneous inductive-recursive definition in intuitionistic type theory is Martin-Löf's universe á la Tarski. A set U 0 of codes for small sets is generated inductively at the same time as a function T 0 , which maps a code to the corresponding small set, is defined by recursion on the way the elements of U 0 are generated. In this paper we argue that there is an underlying general notion of simultaneous inductive-recursive definition (...) which is implicit in Martin-Löf's intuitionistic type theory. We extend previously given schematic formulations of inductive definitions in type theory to encompass a general notion of simultaneous induction-recursion. This enables us to give a unified treatment of several interesting constructions including various universe constructions by Palmgren, Griffor, Rathjen, and Setzer and a constructive version of Aczel's Frege structures. Consistency of a restricted version of the extension is shown by constructing a realisability model in the style of Allen. (shrink)

Review by: Alexander G. Melnikov The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 400-401, September 2013.

This article advocates for a hermeneutic model for children-AI (age group 7–11 years) interactions in which the desirable purpose of children’s interaction with artificial intelligence (AI) systems is children's growth. The article perceives AI systems with machine-learning components as having a recursive element when interacting with children. They can learn from an encounter with children and incorporate data from interaction, not only from prior programming. Given the purpose of growth and this recursive element of AI, the article (...) argues for distinguishing the interpretation of bias within the artificial intelligence (AI) ethics and responsible AI discourse. Interpreting bias as a preference and distinguishing between positive (pro-diversity) and negative (discriminative) bias is needed as this would serve children's healthy psychological and moral development. The human-centric AI discourse advocates for an alignment of capacities of humans and capabilities of machines by a focus both on the purpose of humans and on the purpose of machines for humans. The emphasis on mitigating negative biases through data protection, AI law, and certain value-sensitive design frameworks demonstrates that the purpose of the machine for humans is prioritized over the purpose of humans. These top–down frameworks often narrow down the purpose of machines to do-no-harm and they miss accounting for the bottom-up views and developmental needs of children. Therefore, applying a growth model for children-AI interactions that incorporates learning from negative AI-mediated biases and amplifying positive ones would positively benefit children’s development and children-centric AI innovation. Consequently, the article explores:What challenges arise from mitigating negative biases and amplifying positive biases in children-AI interactions and how can a growth model address these?To answer this, the article recommends applying a growth model in open AI co-creational spaces with and for children. In such spaces human–machine and human–human value alignment methods can be collectively applied in such a manner that children can (1) become sensitized toward the effects of AI-mediated negative biases on themselves and others; (2) enable children to appropriate and imbue top-down values of diversity, and non-discrimination with their meanings; (3) enforce children’s right to identity and non-discrimination; (4) guide children in developing an inclusive mindset; (5) inform top-down normative AI frameworks by children’s bottom-up views; (6) contribute to design criteria for children-centric AI. Applying such methods under a growth model in AI co-creational spaces with children could yield an inclusive co-evolution between responsible young humans in the loop and children-centric AI systems. (shrink)

We give a survey of automorphisms of countable recursively saturated models of Peano Arithmetic.

A model of Peano Arithmetic is short recursively saturated if it realizes all its bounded finitely realized recursive types. Short recursively saturated models of $\PA$ are exactly the elementary initial segments of recursively saturated models of $\PA$. In this paper, we survey and prove results on short recursively saturated models of $\PA$ and their automorphisms. In particular, we investigate a certain subgroup of the automorphism group of such models. This subgroup, denoted $G|_{M(a)}$, contains all the automorphisms of a (...) countable short recursively saturated model of which can be extended to an automorphism of the countable recursively saturated elementary end extension of the model. (shrink)